import java.util.*;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
 *
 */
public class Solution {

    private static final char[][] arr = new char[10][];

    static {
        arr[2] = new char[]{'a', 'b', 'c'};
        arr[3] = new char[]{'d', 'e', 'f'};
        arr[4] = new char[]{'g', 'h', 'i'};
        arr[5] = new char[]{'j', 'k', 'l'};
        arr[6] = new char[]{'m', 'n', 'o'};
        arr[7] = new char[]{'p', 'q', 'r', 's'};
        arr[8] = new char[]{'t', 'u', 'v'};
        arr[9] = new char[]{'w', 'x', 'y', 'z'};
    }

    public List<String> letterCombinations(String digits) {
        if (Objects.isNull(digits) || digits.length() == 0) {
            return Collections.emptyList();
        }
        char[] digitCharArr = digits.toCharArray();
        char[] one = new char[digitCharArr.length];
        List<String> result = new ArrayList<>();

        iteration(digitCharArr, 0, one, result);
        return result;
    }

    public static void iteration(char[] digitCharArr, int index, char[] one, List<String> result) {
        int i = digitCharArr[index] - 48;
        if (index < digitCharArr.length - 1) {
            for (Character c : arr[i]) {
                one[index] = c;
                iteration(digitCharArr, index + 1, one, result);
            }
        } else {
            for (Character c : arr[i]) {
                one[index] = c;
                result.add(new String(one));
            }
        }
    }

}